//https://www.nowcoder.com/practice/f836b2c43afc4b35ad6adc41ec941dba?tpId=13&tqId=23254&ru=/exam/oj/ta&qru=/ta/coding-interviews/question-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13
//思想1:1.在原有链表上复制一个新节点出来；2.设置新节点的random指针指向；3.分离原有的链表出来；
//思想2:1.复制一条新的链表出来；2.哈希表，保存复制节点的映射关系；（这里用到新特性，结构化绑定！！！）
// comments：good

#include <iostream>
#include <vector>
#include <stack>
#include <unordered_map>

using namespace std;

struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(nullptr), random(nullptr) {
    }
};

class Solution1 {
  public:
    RandomListNode* Clone(RandomListNode* pHead) {
        if (!pHead) return nullptr;
        RandomListNode* cur = pHead;
        // copy node
        while (cur) {
            RandomListNode* clone = new RandomListNode(cur->label);
            //clone->label = head->label;
            clone->next = cur->next;
            cur->next = clone;
            cur = clone->next;
        }
        // set random ptr
        cur = pHead;
        RandomListNode* clone_p;
        while (cur) {
            clone_p = cur->next;
            if (cur->random != nullptr) clone_p->random = cur->random->next;
            cur = clone_p->next;
        }

        // detach two list
        cur = pHead;
        RandomListNode* cur_clone = cur->next;
        RandomListNode* head_clone = pHead->next;
        while (cur) {
            cur->next = cur_clone->next;
            if (cur_clone->next)
                cur_clone->next = cur->next->next;
            cur = cur->next;
            cur_clone = cur_clone->next;
        }
        return head_clone;
    }
};


class Solution2 {
public:
    RandomListNode* Clone(RandomListNode* pHead) {
        if(!pHead) return pHead;    // 为空则直接返回空
        unordered_map<RandomListNode*, RandomListNode*> mp;    // 创建哈希表
 
        RandomListNode* dummy = new RandomListNode(0);    // 哨兵节点
 
        RandomListNode *pre = dummy, *cur = pHead;    // 指向哨兵和链表头的指针
 
        while(cur){
            RandomListNode* clone = new RandomListNode(cur->label);    // 拷贝节点
            pre->next = clone;    // 与上个结点连接
            mp[cur] = clone;    // 记录映射关系
            pre = pre->next;    // 指针移动
            cur = cur->next;
        }
        cur=pHead;
        while(cur){
           auto mirror=mp[cur];
           if(cur->random==nullptr){
            mirror->random=nullptr;
           }else{
            mirror->random=mp[cur->random];
           }
           cur=cur->next;
        }
 
        // for(auto& [key, value] : mp){    // 遍历哈希表
        //     value->random = key->random == NULL ? NULL : mp[key->random];
        // }
 
        delete dummy;    // 释放哨兵节点空间
        return mp[pHead];
    }
};